#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<vector>
#include<stack>
using namespace std;

typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
}TreeNode;

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> ans;
    stack<TreeNode*> s;
    s.push(root);
    while (!s.empty()) {
        TreeNode* r = s.top();
        s.pop();
        if (!r) continue;
        ans.push_back(r->val);
        s.push(r->right);
        s.push(r->left);
    }
    return ans;
}

TreeNode* CreateTreeNode(int val)
{
    TreeNode* Node = (TreeNode*)malloc(sizeof(TreeNode));
    Node->val = val;
    Node->left = NULL;
    Node->right = NULL;

    return Node;
}

int main()
{
    TreeNode* n1 = CreateTreeNode(1);
    TreeNode* n2 = CreateTreeNode(2);
    TreeNode* n3 = CreateTreeNode(3);
    TreeNode* n4 = CreateTreeNode(4);
    TreeNode* n5 = CreateTreeNode(5);
    TreeNode* n6 = CreateTreeNode(6);
    
    n1->left = n2;
    n1->right = n3;
    n2->left = n4;
    n2->right = n5;
    n3->left = n6;

    vector<int> res = preorderTraversal(n1);
    for (int i = 0; i < res.size(); i++)
        printf("%d ", res[i]);

    return 0;
}